题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

$0 <= 数组长度 <= 50000$

---

算法

(归并排序) $O(nlogn)$

归并排序的过程中计算逆序对的数量，更精细的来说是在合并两个有序序列时计算逆序对的数量，对于两个有序序列，如 $\{4, 5\}$ 和 $\{1, 2\}$，i 和 j 指向序列的第一个元素 $i = 0, j = 3, mid = 1$，对于 $1$ 可以构成两个逆序对 $<4, 1>$ 和 $<5, 1>$ 即 mid - i + 1 = 2，同样对于 2 也有两个逆序对 $<4, 2>$ 和 $<5, 2>$，即 mid - i + 1 = 2。

$mid - i + 1$ 表示的是区间 $[i, mid]$ 的长度，依然拿上面的例子看，对于 $4$ 来说，$4$ 可以和 $1$ 构成逆序对，由于是有序序列，那么 $4$ 之后的数同样也可以和 $1$ 构成逆序对，即区间 $[i, mid]$ 的元素个数就是和 $j$ 可以构成的逆序对个数$。

所以当 $nums[i] > nums[j]$ 时更新逆序对的数量即可。

时间复杂度

归并排序的时间复杂度为 $O(nlogn)$。

空间复杂度

临时数组需要 $O(n)$ 的空间。

C++ 代码

class Solution {
public:
    int merge(vector<int>& nums, vector<int>& tmp, int l, int r) {
        if (l >= r) return 0;
        int mid = l + r >> 1;
        int res = merge(nums, tmp, l, mid) + merge(nums, tmp, mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) tmp[k ++ ] = nums[i ++ ];
            else { // nums[i] > nums[j]，则 [i, mid] 和 j 都可以构成逆序对
                res += mid - i + 1;
                tmp[k ++ ] = nums[j ++ ];
            }
        }

        while (i <= mid) tmp[k ++ ] = nums[i ++ ];
        while (j <= r) tmp[k ++ ] = nums[j ++ ];

        for (int i = l, k = 0; i <= r; i ++ ) nums[i] = tmp[k ++ ];
        return res;
    }

    int reversePairs(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> tmp(nums.size());
        return merge(nums, tmp, 0, nums.size() - 1);
    }
};